|
In computer science, a scapegoat tree is a self-balancing binary search tree, invented by Arne Andersson and again by Igal Galperin and Ronald L. Rivest. It provides worst-case ''O''(log ''n'') lookup time, and ''O''(log ''n'') amortized insertion and deletion time. Unlike most other self-balancing binary search trees that provide worst case ''O''(log ''n'') lookup time, scapegoat trees have no additional per-node memory overhead compared to a regular binary search tree: a node stores only a key and two pointers to the child nodes. This makes scapegoat trees easier to implement and, due to data structure alignment, can reduce node overhead by up to one-third. ==Theory== A binary search tree is said to be weight-balanced if half the nodes are on the left of the root, and half on the right. An α-weight-balanced node is defined as meeting a relaxed weight balance criterion: size(left) <= α *size(node) size(right) <= α *size(node) Where size can be defined recursively as: function size(node) if node = nil return 0 else return size(node->left) + size(node->right) + 1 end An α of 1 therefore would describe a linked list as balanced, whereas an α of 0.5 would only match almost complete binary trees. A binary search tree that is α-weight-balanced must also be α-height-balanced, that is height(tree) <= log1/α(NodeCount) + 1 Scapegoat trees are not guaranteed to keep α-weight-balance at all times, but are always loosely α-height-balanced in that height(scapegoat tree) <= log1/α(NodeCount) + 1 This makes scapegoat trees similar to red-black trees in that they both have restrictions on their height. They differ greatly though in their implementations of determining where the rotations (or in the case of scapegoat trees, rebalances) take place. Whereas red-black trees store additional 'color' information in each node to determine the location, scapegoat trees find a scapegoat which isn't α-weight-balanced to perform the rebalance operation on. This is loosely similar to AVL trees, in that the actual rotations depend on 'balances' of nodes, but the means of determining the balance differs greatly. Since AVL trees check the balance value on every insertion/deletion, it is typically stored in each node; scapegoat trees are able to calculate it only as needed, which is only when a scapegoat needs to be found. Unlike most other self-balancing search trees, scapegoat trees are entirely flexible as to their balancing. They support any α such that 0.5 < α < 1. A high α value results in fewer balances, making insertion quicker but lookups and deletions slower, and vice versa for a low α. Therefore in practical applications, an α can be chosen depending on how frequently these actions should be performed. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Scapegoat tree」の詳細全文を読む スポンサード リンク
|